/**
 * 给定整数数组nums和整数k,请返回数组中第k个最大的元素
 * 请注意，你需要找的是数组排序后的第K个最大的元素，而不是k个不同的元素。
 * 你必须设计并实现时间复杂度为O(n)的算法解决此问题
 * 示例1:
 *  输入: [3, 2, 1, 5, 6, 4], k = 2
 *  输出: 5
 * 示例2:
 *  输入: [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
 *  输出: 4
*/

function findKthLargest(nums, k) {
    const target = findBaseValue(nums)
    return target[target.length-k] ;
}

// 快速排序
// 快排入口算法
// 找到基准值
function findBaseValue(nums) {
    // 校验入参防止无限执行
    if (!nums) return []
    if (nums.length <= 1) return nums;
    // 以第一个值为基准值
    const base = nums[0];
    // 左右下标
    let i = 1;
    let j = nums.length - 1;
    // 左右数组
    const l = [];
    const r = [];
    // 依次对比左右数据
    while (i <= j) {
        if (nums[i] > base) {
            r.push(nums[i]);
        } else {
            l.push(nums[i]);
        }
        // 如果左右下标重复只执行一次
        if (i !== j) {
            if (nums[j] > base) {
                r.push(nums[j]);
            } else {
                l.push(nums[j]);
            }
        }
        i++;
        j--;
    }
    return [...findBaseValue(l), nums[0], ...findBaseValue(r)]
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4));